#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
using namespace std;

class Solution1 {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        vector<int>::iterator it = height.begin();
        vector<int>::iterator rit = height.end() - 1;
        int left_high = 0;
        int right_high = 0;
        while (it != height.end()) {
            if (left_high < *it) {
                rit = height.end() - 1;
                while (it < rit) {
                    if (*rit > right_high) {
                        ans = max(ans, int(min(*it, *rit) * (rit - it)));
                        right_high = *rit;
                    }
                    --rit;
                }
                right_high = 0;
                left_high = *it;
            }
            ++it;
        }
        return ans;
    }
};

class Solution2 {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        vector<int>::iterator it = height.begin();
        vector<int>::iterator rit = height.end() - 1;
        while (it != rit) {
            ans = max(ans, int(min(*it, *rit) * (rit - it)));
            if (*it < *rit)
                ++it;
            else
                --rit;
        }
        return ans;
    }
};

class Solution3 {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] < target)left = mid + 1;
            else if (nums[mid] > target)right = mid - 1;
            else return mid;
        }
        if (nums[mid] < target)return mid + 1;
        else return mid;
    }
};

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int begin = 0;
        vector<int> ansv(2, -1);
        while (left <= right) {
            begin = (left + right) / 2;
            if (nums[begin] < target)
                left = begin + 1;
            else if (nums[begin] > target)
                right = begin - 1;
            else break;
        }
        if (begin < 0 || begin >= nums.size() || nums[begin] != target)return ansv;
        int l = begin, r = begin;
        while (l >= 0 && nums[l] == target)--l;
        while (r < nums.size() && nums[r] == target)++r;
        ansv[0] = l + 1;
        ansv[1] = r - 1;
        return ansv;
    }
};